// run: $exec < input
// opt: 0
// flag: -g
#include <iostream>

long long x, m, k, c;

long long quick(int a, int b)
{
	if (!b) return 1 % k;
	long long ret = quick(a, b / 2);
	ret = (ret * ret) % k;
	if (b & 1) ret = (ret * a) % k;
	return ret;
}

long long calc(long long len, int a)
{
	if (len == 1) return 1 % k;
	if (len == 2) return 11 % k;
	long long ret = 0;
	if (len & 1) ret = quick(a, len - 1);
	long long t1 = calc(len / 2, a);
	long long t2 = quick(a, len / 2);
	return (ret + t1 * (1 + t2)) % k;
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	for (int ti = 1; ti <= T; ti++) {
		std::cout << "Case #" << ti << ":\n";
		std::cin >> x >> m >> k >> c;
		long long ans = calc(m, 10);
		ans = (ans * x) % k;
		std::cout << ((ans == c) ? "Yes" : "No") << '\n';
	}
}

